package main

// 题解： https://leetcode-cn.com/problems/escape-a-large-maze/solution/pythonjavajavascriptgo-you-da-xiao-shang-j04b/1326599/

func isEscapePossible(blocked [][]int, source []int, target []int) bool {
	// 1. 边界(10^6): bound，利用hash改善阻碍的线性搜索: block, max: 阻碍最大封闭面积, dir: 规定上下左右移动的行为
	bound, block, max, dir := 1000000, map[int]bool{}, len(blocked)*(len(blocked)-1)/2, [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	// 初始化 block
	for _, b := range blocked {
		block[hash(b)] = true
	}
	// 2. 定义广度优先搜索函数
	// start 代表开始节点，end代表 目标节点。都是 []int 类型slice， [1, 2] 类似这样，长度为2
	bfs := func(start, end []int) bool {
		// 1. list 这里应该是个队列（做广度优先搜索）。在 go标准库中， container/list 双向链表做队列。
		// 这里名字定义为 list，只是个（python列表）slice，尾插就进行到底了，没有头部删除的操作，后面for循环用得到。
		list := [][]int{start}
		// 2. 定义去重map，表示map里面的位置已经遍历过了。 explored 探索过的（等价于used，使用过的）
		explored := map[int]bool{}
		// start位置标记为已处理，加入map（位于list里，就标记是 已处理（或者为待处理））
		explored[hash(start)] = true
		// 3. 开始遍历list里的元素，当 list长度 大于 max，说明不封闭，可以到达target
		for i := 0; i < len(list) && len(list) <= max; i++ {
			// 循环上，下，左，右，四个方向
			for _, d := range dir {
				point := make([]int, 2)
				point[0] = list[i][0] + d[0]
				point[1] = list[i][1] + d[1]
				h := hash(point)
				// （1）如果不越界，（2）没被遍历过(不在list里)，（3）不是阻碍
				if point[0] >= 0 && point[0] < bound && point[1] >= 0 && point[1] < bound && !explored[h] && !block[h] {
					// 如果与end，目标位置一样，说明已经到达目标位置，返回 true
					if point[0] == end[0] && point[1] == end[1] {
						return true
					}
					// 标记为已处理，加入list里
					explored[h] = true
					list = append(list, point)
				}
			}
		}
		// 4. 判断是否封闭， 大于不封闭，小于封闭
		return len(list) > max
	}

	// 细节的地方： 封闭区间可能是 source ，或者在 target位置， 所以都要试一下。
	return bfs(source, target) && bfs(target, source)
}

// python中的元组 tuple是可hash的。而 go中的slice是不可hash的
// 这里巧妙的自定义一个hash函数，用于hash slice 切片
// 官方常用的方法是构造 结构体，表示坐标。是可hash的。代替长度为 2的slice表示
// 这里涉及到了一个 go map知识点，什么样的数据结构可以作为 map的 key？查阅相关资料有下面这些：
/*
	1. 除了 slice， map， function 的内建类型都可以key
	2. Struct类型 不包含上述字段， 也可以作为 key。(在编译的时候检查的)
	3. var m map[int]int 不能直接使用（m[1] = 2, nil不能直接使用）
	4. 而 slcie ， var s []int, append（s, 1） nil 可以直接使用。
*/
func hash(point []int) int {
	return point[0]*1000000 + point[1]
}
